﻿#pragma once
#include <iostream>
#include <cassert>

#if 0

namespace simulation {

	template<class T>
	class vector {
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		/*
			构造函数
		*/

		//默认构造
		vector()
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{}

		vector(size_t n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			resize(n, val);
		}

		// 如果没有该构造函数，当T为int类型时，如vector(1,1)会调用vector(inputIterator first, inputIterator last)而不是vector(size_t n, const T& val = T())
		vector(int n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			resize(n, val);
		}

		template<class inputIterator>
		vector(inputIterator first, inputIterator last)
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			while (first != last)
			{
				push_back(*first); // this->push_back(*first)
				++first;
			}
		}


		vector(const vector<T>& vT)
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(vT.capacity());
			for (const auto& k : vT)
			{
				push_back(k);
			}
		}

		~vector()
		{
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}

		vector<T>& operator=(const vector<T>& vT)
		{
			if (this != &vT)
			{
				vector<T> temp(vT);
				swap(temp);
			}

			return *this;
		}


		/*
			迭代器
		*/
		iterator begin()
		{
			return _start;
		}

		const_iterator begin() const
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator end() const
		{
			return _finish;
		}

		/*
			容量相关
		*/

		//得到vector的有效长度
		size_t size() const
		{
			return _finish - _start;
		}

		//得到vector的容量
		size_t capacity() const
		{
			return _end_of_storage - _start;
		}

		void resize(size_t n, const T& val = T())
		{
			if (n <= size())
			{
				//情况一：n小于size()时 直接改变标志着有效长度的_finish 
				//因为正常调用api是不能访问到_finish后面的数据的 间接达到了删除的目的
				//当n == size()时 下面的语句可以视为_finish = _finish
				_finish = _start + n;
			}
			else
			{
				//提前扩容 然后把val一个一个插入进去 同时还能调整_finish的位置
				//_start + n为resize后_finish应该在的位置
				reserve(n);
				while (_finish != _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

		//判断vector是否为空
		bool empty() const
		{
			return _start == _finish;
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldSize = size();

				iterator temp = new T[n];

				//避免因_start为nullptr时造成的错误 空指针不能被解引用
				if (_start)
				{
					for (size_t i = 0; i < oldSize; ++i)
					{
						temp[i] = _start[i];
					}

				}

				//空指针可以被delete 所以delete放在 if (_start)外面统一处理
				//因为delete会检查被delete的目标是否为空指针 如果是空指针则不做处理
				//一定要先delete再给_start赋值 不然会找不到_start指向的旧空间 这样会内存泄漏
				delete[] _start;
				_start = temp;
				_finish = _start + oldSize;
				_end_of_storage = _start + n;

			}
		}

		/*
			元素访问
		*/

		T& operator[](size_t pos)
		{
			assert(pos >= 0 && pos < size());

			return _start[pos];
		}

		const T& operator[](size_t pos) const
		{
			assert(pos >= 0 && pos < size());

			return _start[pos];
		}

		T& front()
		{
			return *_start;
		}

		const T& front() const
		{
			return *_start;
		}

		T& back()
		{
			return *(_finish - 1);
		}

		const T& back() const
		{
			return *(_finish - 1);
		}

		/*
			修改相关
		*/

		void push_back(const T& val = T())
		{
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 2 : 2 * capacity());
			}

			*_finish = val;
			++_finish;
		}

		void pop_back()
		{
			//判断vector内是否为空 同时也能判断_start是否为空指针
			//因为当_start为空指针是_finish也一定为空指针 空指针不可能会大于另一个空指针
			assert(_finish > _start);

			--_finish;
		}

		iterator insert(iterator pos, const T& val)
		{
			assert(pos >= _start && pos <= _finish);

			if (_finish == _end_of_storage)
			{
				//记录pos到_start的距离
				size_t len = pos - _start;

				reserve(capacity() == 0 ? 2 : 2 * capacity());

				//如果发生了增容 就需要重置pos 因为pos发生了迭代器失效
				pos = _start + len;
			}

			//从后开始挪动数据 为将插入的数据腾出位置
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}

			*pos = val;
			++_finish;

			//返回值为第一个新插入的数据
			return pos;
		}

		iterator erase(iterator pos)
		{
			//同时检查下标有效性和vector是否为空
			//当容器为空时 _start == _finish，所以下面的语句在vector为空时可改成 assert(pos >= _start && pos < _start)
			//显然 >= 和 < 不可能同时成立 
			assert(pos >= _start && pos < _finish);

			iterator begin = pos;
			while (begin < _finish)
			{
				*begin = *(begin + 1);
				++begin;
			}

			--_finish;
			return pos;
		}

		void swap(vector<T>& vT)
		{
			std::swap(_start, vT._start);
			std::swap(_finish, vT._finish);
			std::swap(_end_of_storage, vT._end_of_storage);
		}

		void clear()
		{
			_finish = _start;
		}

	private:
		iterator _start; // 堆空间的起始位置
		iterator _finish; // 最后一个有效元素的后继位置
		iterator _end_of_storage; // 最后一个有效空间的后继位置
	};
}

#endif

#if 0

template<class T>
struct Allocator
{
	T* allocate(size_t size)
	{
		return (T*)malloc(sizeof(T) * size);
	}

	void deallocate(T* pointer)
	{
		free(pointer);
	}

	void construct(T* pointer, const T& val)
	{
		new (pointer) T(val);
	}

	void destroy(T* pointer)
	{
		pointer->~T();
	}
};

template<class T, class Alloc = Allocator<T>>
class vector {
public:
	typedef T* iterator;
	typedef const T* const_iterator;

public:
	vector()
		: _start(nullptr)
		, _finish(nullptr)
		, _end_of_storage(nullptr)
	{}

	~vector()
	{
		delete[] _start;
		_start = _finish = _end_of_storage = nullptr;
	}

	//得到vector的有效长度
	size_t size() const
	{
		return _finish - _start;
	}

	//得到vector的容量
	size_t capacity() const
	{
		return _end_of_storage - _start;
	}

	void resize(size_t n, const T& val = T())
	{
		if (n <= size())
		{
			//情况一：n小于size()时 直接改变标志着有效长度的_finish 
			//因为正常调用api是不能访问到_finish后面的数据的 间接达到了删除的目的
			//当n == size()时 下面的语句可以视为_finish = _finish
			_finish = _start + n;
		}
		else
		{
			//提前扩容 然后把val一个一个插入进去 同时还能调整_finish的位置
			//_start + n为resize后_finish应该在的位置
			reserve(n);
			while (_finish != _start + n)
			{
				*_finish = val;
				++_finish;
			}
		}
	}

	//判断vector是否为空
	bool empty() const
	{
		return _start == _finish;
	}

	void reserve(size_t n)
	{
		if (n > capacity())
		{
			size_t oldSize = size();

			iterator temp = new T[n];

			//避免因_start为nullptr时造成的错误 空指针不能被解引用
			if (_start)
			{
				for (size_t i = 0; i < oldSize; ++i)
				{
					temp[i] = _start[i];
				}

			}

			//空指针可以被delete 所以delete放在 if (_start)外面统一处理
			//因为delete会检查被delete的目标是否为空指针 如果是空指针则不做处理
			//一定要先delete再给_start赋值 不然会找不到_start指向的旧空间 这样会内存泄漏
			delete[] _start;
			_start = temp;
			_finish = _start + oldSize;
			_end_of_storage = _start + n;

		}
	}

	T& operator[](size_t pos)
	{
		assert(pos >= 0 && pos < size());

		return _start[pos];
	}

	const T& operator[](size_t pos) const
	{
		assert(pos >= 0 && pos < size());

		return _start[pos];
	}

	void push_back(const T& val = T())
	{
		if (_finish == _end_of_storage)
		{
			reserve(capacity() == 0 ? 2 : 2 * capacity());
		}

		*_finish = val;
		++_finish;
	}

	void pop_back()
	{
		//判断vector内是否为空 同时也能判断_start是否为空指针
		//因为当_start为空指针是_finish也一定为空指针 空指针不可能会大于另一个空指针
		assert(_finish > _start);

		--_finish;
	}


private:
	iterator _start; // 堆空间的起始位置
	iterator _finish; // 最后一个有效元素的后继位置
	iterator _end_of_storage; // 最后一个有效空间的后继位置
	Alloc _allocator; // 空间配置器
};

#endif

namespace simulation {

	// 空间配置器起的作用主要是将new和delete的功能给拆分开
	// new 拆分-> 申请空间 和 调用构造函数
	// delete 拆分 -> 调用析构函数 和 释放空间
	template<class T>
	struct Allocator
	{
		// 用于申请空间
		T* allocate(size_t num)
		{
			return (T*)malloc(sizeof(T) * num);
		}

		// 用于释放空间
		void deallocate(T* pointer)
		{
			free(pointer);
		}

		// 用于在已经申请的空间上调用对象的构造函数来创建对象
		void construct(T* pointer, const T& val)
		{
			//定位new表达式
			new (pointer) T(val); // 调用拷贝构造来创建对象
		}

		void construct(T* pointer, T&& val)
		{
			new (pointer) T(std::move(val)); // 调用移动构造来创建对象
		}

		// 销毁对象
		void destroy(T* pointer)
		{
			pointer->~T(); // 调用析构函数来销毁对象
		}
	};

	template<class T, class Alloc = Allocator<T>>
	class vector {
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		/*
			构造函数
		*/

		//默认构造
		vector(const Alloc& allocator = Alloc())
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
			, _allocator(allocator)
		{}

		vector(size_t n, const T& val = T(), const Alloc& allocator = Alloc())
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
			, _allocator(allocator)
		{
			resize(n, val);
		}

		// 如果没有该构造函数，当T为int类型时，如vector(1,1)会调用vector(inputIterator first, inputIterator last)而不是vector(size_t n, const T& val = T())
		//vector(int n, const T& val = T(), const Alloc& allocator = Alloc())
		//	: _start(nullptr)
		//	, _finish(nullptr)
		//	, _end_of_storage(nullptr)
		//	, _allocator(allocator)
		//{
		//	resize(n, val);
		//}

		// 效果同上，使用了C++11的委托构造函数
		vector(int n, const T& val = T(), const Alloc& allocator = Alloc())
			: vector(static_cast<size_t>(n), val, allocator)
		{}

		template<class inputIterator>
		vector(inputIterator first, inputIterator last, const Alloc& allocator = Alloc())
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
			, _allocator(allocator)
		{
			while (first != last)
			{
				push_back(*first); // this->push_back(*first)
				++first;
			}
		}


		vector(const vector<T>& vec)
			: _start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
			, _allocator(vec._allocator)
		{
			reserve(vec.capacity());
			for (const auto& value : vec)
			{
				push_back(value);
			}
		}

		~vector()
		{
			//delete[] _start;
			//_start = _finish = _end_of_storage = nullptr;

			for (iterator now = _start; now != _finish; ++now)
			{
				_allocator.destroy(now); // 销毁有效对象
			}

			_allocator.deallocate(_start); // 回收开辟的空间

			_start = _finish = _end_of_storage = nullptr;
		}

		vector<T>& operator=(const vector<T>& vT)
		{
			if (this != &vT)
			{
				vector<T> temp(vT);
				swap(temp);
			}

			return *this;
		}


		/*
			迭代器
		*/
		iterator begin()
		{
			return _start;
		}

		const_iterator begin() const
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator end() const
		{
			return _finish;
		}

		/*
			容量相关
		*/

		//得到vector的有效长度
		size_t size() const
		{
			return _finish - _start;
		}

		//得到vector的容量
		size_t capacity() const
		{
			return _end_of_storage - _start;
		}

		void resize(size_t n, const T& val = T())
		{
			if (n <= size())
			{
				//情况一：n小于size()时 直接改变标志着有效长度的_finish 
				//因为正常调用api是不能访问到_finish后面的数据的 间接达到了删除的目的
				//当n == size()时 下面的语句可以视为_finish = _finish
				//_finish = _start + n;

				while (_finish != _start + n)
				{
					--_finish;
					_allocator.destroy(_finish);
				}
			}
			else
			{
				//提前扩容 然后把val一个一个插入进去 同时还能调整_finish的位置
				//_start + n为resize后_finish应该在的位置
				reserve(n);
				while (_finish != _start + n)
				{
					//*_finish = val;
					_allocator.construct(_finish, val);
					++_finish;
				}
			}
		}

		//判断vector是否为空
		bool empty() const
		{
			return _start == _finish;
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldSize = size(); // 记录原来容器中数据的多少，方便在扩容后根据_start找到新的_finish

				//iterator temp = new T[n];
				iterator temp = _allocator.allocate(n);

				//避免因_start为nullptr时造成的错误 空指针不能被解引用
				if (_start)
				{
					for (size_t i = 0; i < oldSize; ++i)
					{
						//temp[i] = _start[i];
						_allocator.construct(temp + i, std::move(_start[i]));
					}

				}

				//空指针可以被delete 所以delete放在 if (_start)外面统一处理
				//因为delete会检查被delete的目标是否为空指针 如果是空指针则不做处理
				//一定要先delete再给_start赋值 不然会找不到_start指向的旧空间 这样会内存泄漏
				//delete[] _start;

				// 因为原来空间中的数据全部都被转移走了，所以这部分空间可以直接析构
				_allocator.deallocate(_start);

				_start = temp;
				_finish = _start + oldSize;
				_end_of_storage = _start + n;

			}
		}

		/*
			元素访问
		*/

		T& operator[](size_t pos)
		{
			assert(pos >= 0 && pos < size());

			return _start[pos];
		}

		const T& operator[](size_t pos) const
		{
			assert(pos >= 0 && pos < size());

			return _start[pos];
		}

		T& front()
		{
			return *_start;
		}

		const T& front() const
		{
			return *_start;
		}

		T& back()
		{
			return *(_finish - 1);
		}

		const T& back() const
		{
			return *(_finish - 1);
		}

		/*
			修改相关
		*/

		void push_back(const T& val = T())
		{
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 2 : 2 * capacity());
			}

			//*_finish = val;
			_allocator.construct(_finish, val);
			++_finish;
		}

		void pop_back()
		{
			//判断vector内是否为空 同时也能判断_start是否为空指针
			//因为当_start为空指针是_finish也一定为空指针 空指针不可能会大于另一个空指针
			assert(_finish > _start);

			//--_finish;
			_allocator.destroy(--_finish);
		}

		// 在指定位置插入，该位置及之后的位置全部向后移动
		iterator insert(iterator pos, const T& val)
		{
			assert(pos >= _start && pos <= _finish);

			if (_finish == _end_of_storage)
			{
				//记录pos到_start的距离
				size_t len = pos - _start;

				reserve(capacity() == 0 ? 2 : 2 * capacity());

				//如果发生了增容 就需要重置pos 因为pos发生了迭代器失效
				pos = _start + len;
			}

			//从后开始挪动数据 为将插入的数据腾出位置
			iterator end = _finish - 1; // 最后一个有效数据的位置
			while (end >= pos)
			{
				*(end + 1) = std::move(*end);
				--end;
			}

			//*pos = val;
			_allocator.construct(pos, val);
			++_finish;

			//返回值为第一个新插入的数据
			return pos;
		}

		iterator erase(iterator pos)
		{
			//同时检查下标有效性和vector是否为空
			//当容器为空时 _start == _finish，所以下面的语句在vector为空时可改成 assert(pos >= _start && pos < _start)
			//显然 >= 和 < 不可能同时成立 
			assert(pos >= _start && pos < _finish);

			iterator begin = pos;
			_allocator.destroy(pos);
			while (begin < _finish)
			{
				*begin = std::move(*(begin + 1));
				++begin;
			}

			--_finish;
			return pos;
		}

		void swap(vector<T>& vT)
		{
			std::swap(_start, vT._start);
			std::swap(_finish, vT._finish);
			std::swap(_end_of_storage, vT._end_of_storage);
			std::swap(_allocator, vT._allocator);
		}

		void clear()
		{
			//_finish = _start;
			for (iterator now = _start; now != _finish; ++now)
			{
				_allocator.destroy(now);
			}

			_finish = _start;
		}

	private:
		iterator _start; // 堆空间的起始位置
		iterator _finish; // 最后一个有效元素的后继位置
		iterator _end_of_storage; // 最后一个有效空间的后继位置
		Alloc _allocator; // 空间配置器
	};
}